#include <bits/stdc++.h>

using namespace std;

// 最长数对链
// 给你一个由n个数对组成的数对数组pairs
// 其中 pairs[i] = [lefti, righti] 且 lefti < righti
// 现在，我们定义一种 跟随 关系，当且仅当 b < c 时
// 数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面
// 我们用这种形式来构造 数对链
// 找出并返回能够形成的最长数对链的长度
// 测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/

class Solution 
{
public:
    int findLongestChain(vector<vector<int>>& pairs) 
    {
        // 数对根据开始位置排序，从小到大
		// 结束位置无所谓！
        sort(pairs.begin(), pairs.end(), [](auto& a, auto& b){
            return a[0] < b[0];
        });

        int n = pairs.size(), len = 0;
        // 结尾的数值
        int ends[n];
        for(int i = 0, find; i < n; ++i)
        {
            find = bs(ends, len, pairs[i][0]);
            if(find == -1) ends[len++] = pairs[i][1];
            else ends[find] = min(ends[find], pairs[i][1]);
        }
        return len;
    }

    // >= num最左位置
    int bs(int* ends, int len, int num)
    {
        int ans = -1, l = 0, r = len - 1, m;
        while(l <= r)
        {
            m = (l + r) >> 1;
            if(num <= ends[m])
            {
                ans = m;
                r = m - 1;
            }
            else l = m + 1;
        }
        return ans;
    }
};


class Solution 
{
public:
    int findLongestChain(vector<vector<int>>& pairs) 
    {
        // 按结束位置排序，从小到大
        sort(pairs.begin(), pairs.end(), [](auto& a, auto& b){
            return a[1] < b[1];
        });
        int n = pairs.size();
        int ret = 0, cur = INT_MIN;
        for(int i = 0; i < n; ++i)
        {
            if(pairs[i][0] > cur)
            {
                cur = pairs[i][1];
                ++ret;
            }
        }        
        return ret;
    }
};